๋ฌธ์
Programmers - ๋ฌธ์์ด ์์ถ
๐ Logic
// ์ ์ฒด ๋ฐ๋ณต์ s ๊ธธ์ด์ ์ ๋ฐ๊น์ง๋ง
for (int len = 1; len <= inputLength / 2; len++) {
int length = 0;
int idx = 0;
// ์๋ฅผ word๊ฐ s์ ๋ฒ์ ์์ ์๋ ๊ฒฝ์ฐ๊น์ง ๋ฐ๋ณต
while(idx + len <= inputLength) {
String word = getWord(idx, len);
int count = 0;
// ํ์ธํ ๋ฌธ์์ด์ด s์ ๋ฒ์ ์์ ์๊ณ , ๊ทธ ๋ฌธ์์ด์ด word์ ๋์ผํ ๊ฒฝ์ฐ
// ๊ทธ ๋ฌธ์์ด์ ๊ฐ์๋ฅผ ๊ตฌํ๋ค.
while (idx + len <= inputLength && word.equals(getWord(idx, len))) {
idx += len;
count++;
}
// count๊ฐ 1์ด๋ฉด ๋ฌธ์์ด ๊ธธ์ด๋ง ๋ํ๊ณ , 1๋ณด๋ค ํฐ ๊ฒฝ์ฐ์๋ ๊ทธ ๊ธธ์ด๋ ํจ๊ป ๋ํ๋ค.
length += word.length() + (count > 1 ? String.valueOf(count).length() : 0);
}
// ๋จ์ ๋ฌธ์์ด ๋ถ์ด๊ธฐ
length += inputLength - idx;
minLength = Math.min(minLength, length);
}
- ๋ฌธ์์ด์ 1๋ถํฐ ์ฃผ์ด์ง ๋ฌธ์์ด ๊ธธ์ด์ ์ ๋ฐ๊น์ง๋งํผ ์๋ฅด๋ ๊ฒ์ ๋ฐ๋ณตํ๋ค.
- ์ ํ ๊ธธ์ด๋งํผ ๋ฌธ์์ด์ ๋น๊ตํ๊ณ ๊ฐ์์ ์ ํ ๊ธธ์ด๋งํผ์
length์ ๋ํด, ์ต์ข ์ ์ผ๋กminLength๋ฅผ ์ต์ ํํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.util.*;
class Solution {
static String inputString;
public int solution(String s) {
if (s.length() == 1) return 1;
inputString = s;
int inputLength = s.length();
int minLength = Integer.MAX_VALUE;
// ์ ์ฒด ๋ฐ๋ณต์ s ๊ธธ์ด์ ์ ๋ฐ๊น์ง๋ง
for (int len = 1; len <= inputLength / 2; len++) {
int length = 0;
int idx = 0;
// ์๋ฅผ word๊ฐ s์ ๋ฒ์ ์์ ์๋ ๊ฒฝ์ฐ๊น์ง ๋ฐ๋ณต
while(idx + len <= inputLength) {
String word = getWord(idx, len);
int count = 0;
// ํ์ธํ ๋ฌธ์์ด์ด s์ ๋ฒ์ ์์ ์๊ณ , ๊ทธ ๋ฌธ์์ด์ด word์ ๋์ผํ ๊ฒฝ์ฐ
// ๊ทธ ๋ฌธ์์ด์ ๊ฐ์๋ฅผ ๊ตฌํ๋ค.
while (idx + len <= inputLength && word.equals(getWord(idx, len))) {
idx += len;
count++;
}
// count๊ฐ 1์ด๋ฉด ๋ฌธ์์ด ๊ธธ์ด๋ง ๋ํ๊ณ , 1๋ณด๋ค ํฐ ๊ฒฝ์ฐ์๋ ๊ทธ ๊ธธ์ด๋ ํจ๊ป ๋ํ๋ค.
length += word.length() + (count > 1 ? String.valueOf(count).length() : 0);
}
// ๋จ์ ๋ฌธ์์ด ๋ถ์ด๊ธฐ
length += inputLength - idx;
minLength = Math.min(minLength, length);
}
return minLength;
}
private String getWord(int start, int len) {
return inputString.substring(start, start + len);
}
}
โ๏ธ Review
- ์ ์ผ ๋จผ์ ๊ทธ๋ฆฌ๋ํ ๋ฐฉ๋ฒ์ ๋ ์ฌ๋ฆฌ๊ธด ํ์ผ๋, ์๊ฐ ์ด๊ณผ๊ฐ ๋์ง ์์๊น ์๊ฐํ๋ค.
- ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ ์ต๋ 1000์ด์๊ณ , ์ด์ฐจํผ ๋ฌธ์์ด ๋น๊ต๋ฅผ ์ํด ์ ๋ฐ ๊ธธ์ด๊น์ง๋ง ์๋ฅผ ๊ฒ์ด๋ฏ๋ก ๊ด์ฐฎ์ ๊ฒ ๊ฐ์๋ค.